package Sort_Work;

import java.util.Arrays;

/**
 * 希尔排序（像是插入排序的升级版
 * 时间复杂度：不好算
 * 空间复杂度：O（1）
 * 稳定性：不稳定
 */
public class Shell_Sort {
    public static void shellSort(int[] array) {
        int gap = array.length;
        while(gap > 1) {
            gap = gap / 3 + 1;
            //gap /= 2;   (两种都可以
            shell(array,gap);
        }
    }
    public static void shell(int[] array,int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0 ; j -= gap) {
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                } else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] array = {1,3,5,7,9,2,4,6,8};
        shellSort(array);
        System.out.println(Arrays.toString(array));
    }
}